#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;
// 169. 多数元素
// 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
// https://leetcode.cn/problems/majority-element/description/

// 排序方法
// Time Complexity: O(nlogn)
// Space Complexity: O(1)
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        assert(nums.size() > 0);

        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};
int main() {
    vector<int> nums1 = {3, 2, 3};

    cout << Solution().majorityElement(nums1) << endl;

    nums1 = {2,2,1,1,1,2,2};
    cout << Solution().majorityElement(nums1) << endl;
    return 0;
}
